/*
** EPITECH PROJECT, 2018
** AlgorithmCode
** File description:
** Red Black Tree
*/

#ifndef RBTREE_H_
	#define RBTREE_H_

/**
 * 红黑树实现.
 */

#include <functional>
#include "BinaryTree.h"
#include <cassert>

struct RBAttribute

	enum COLOR_DEF{
		BLOCK = 0,
		RED = 1
	};
	int Color : 1; //0(block) or 1(red)
	size_t undef : 31; // 0 ~ 2^31 - 1, ????并未定义与使用.

	RBAttribute(const RBAttribute& other):Color(other.Color){

	}

	RBAttribute():Color(RED), BlockCount(0){

	}

	bool IsRed(){
		return ((Color & 0x80000000) >> 31) == static_cast<int>(COLOR_DEF::RED) ? true : false; 
	}

	bool IsBlock(){
		return Color == static_cast<int>(COLOR_DEF::BLOCK) ? true : false;
	}
};

class RBTree;

template<typename T, typename compare = std::less<T>>
struct RBTreeNode:public TreeNode<T, compare>{
	RBAttribute RBColor;

	RBTreeNode* pParent;
	
	RBTreeNode(T* pElem, RBTreeNode* pL = nullptr, RBTreeNode* pR = nullptr, RBTreeNode* pP = nullptr)
		:pParent(pP),TreeNode<T, compare>(pElem, pL, pR){

		}
	RBTreeNode():pParent(nullptr){

	}

	RBTreeNode* Left(){
		return (RBTreeNode*)(this->pLeft);
	}

	RBTreeNode* Right(){
		return (RBTreeNode*)(this->pRight);
	}

	RBTreeNode* Parent(){
		return pParent;
	}

	void SetLeft(RBTreeNode* pNode){
		this->pLeft = pNode;
	}

	void SetRight(RBTreeNode* pNode){
		this->pRight = pNode;
	}

	void SetParent(RBTreeNode* pNode){
		this->pParent = pNode;
	}

	T* ELem(){
		return this->pElem;
	}

	template<typename T, typename compare>
	friend class RBTree;
};

/**
 * 红黑树的删除操作依赖与NIL节点，所以不能单纯使用nullptr.
 * 添加Del操作时需要添加附带信息.
 */
template<typename T, typename compare = std::less<T>>
class RBTree{
public:
	typedef RBTreeNode<T, compare> NodeType;
	typedef T ELEM_TYPE;
	typedef compare COMPARE;
public:
	RBTree():root(nullptr){
	}

	~RBTree(){

	}

	const NodeType*const Find(const T& value)const{
		if(root)
			return static_cast<NodeType *>(root->FindValue(value, nullptr).first);

		return nullptr;
	}

	NodeType* Del(const T& value){
		NodeType* pNode = static_cast<NodeType *>(root->FindValue(value, nullptr).first);
		if(pNode){
			NodeType* pTmp = pNode;
			NodeType* pSubseque = nullptr; //后继,也就是出现问题的需要修复的节点。
			NodeType* pSubParent = nullptr; //需要的附带信息,若不为空则指向出问题的父节点.
			char cTmp = 0;
			//记录需要移动的节点颜色
			RBAttribute attr = pNode->RBColor;
			if(pNode->Left() == nullptr){
				//左子节点为空的情况，也可能使得右子节点为空.
				/* 使得pNode节点的父节点指向其右子节点，也可能指向空 */
				pSubseque = pNode->Right();
				//pSubseque == nullptr时赋值
				if(!pSubseque){
					pSubParent = pNode->Parent(); //其父，此地方是开始出现破坏性质的节点
				}

				cTmp = TransPlant(pNode, pNode->Right());
			}else
			if(pNode->Right() == nullptr){
				//此时左子节点一定不为空，而右子节点为空.
				/* 使得其父节点指向左子节点. */
				pSubseque = pNode->Left();
				//pSubseque == nullptr时赋值
				if(!pSubseque){
					pSubParent = pNode->Parent(); //其父，此地方是开始出现破坏性质的节点
				}

				cTmp = TransPlant(pNode, pNode->Left());
			}else{
				//两个节点都不为空.
				pTmp = pNode->Right()->GetMinimum();
				//此时，寻找pNode节点的后继节点.
				/* 后继就存在pNode的右子树中，右子节点也会是pNode的后继. */
				attr = pTmp->RBColor; //pTmp 一定不为nullptr
				pSubseque = pTmp->Right();//pSubseque，可能为nullptr

				/* 画个图模拟一下就知道了. */
				/* 后面的代码则是寻找到了后继节点使得交换其节点的左右父指向 */
				if(pTmp->Parent() == pNode){
					if(pSubseque)
						pSubseque->SetParent(pTmp);
					else{
						//pSubseque == nullptr时赋值
						pSubParent = pNode->Parent(); //
					}
				}else{
					//pSubseque == nullptr时赋值
					if(pTmp->Right() == nullptr)
						pSubParent = pTmp->Parent();

					cTmp = TransPlant(pTmp, pTmp->Right());//后继节点移出来.
					pTmp->SetRight(pNode->Right());//设置为当其后继
					if(pNode->Right()){
						pNode->Right()->SetParent(pTmp);
					}
				}
				//这里则是更改pNode的指向并变为pNode的颜色(相当于变向的删除了其替换节点的颜色).
				TransPlant(pNode, pTmp);
				pTmp->SetLeft(pNode->Left());
				pTmp->Left()->SetParent(pTmp);
				pTmp->RBColor.Color = pNode->RBColor.Color;
			}

			if(attr.IsBlock()){
				DelFixup(pSubseque, {pSubParent, cTmp});
			}
		}
	}

	void Add(T* pElem){
		assert(pElem);

		if(root){
			//寻找合适的位置
			NodeType* pParent = nullptr;
			NodeType* pTmp = root;
			COMPARE comp;
			char mark = 0;
			while(pTmp){
				pParent = pTmp;
				if(comp(*pElem, *pTmp->ELem())){ // <
					pTmp = pTmp->Left();
					mark = -1;
				}else{
					pTmp = pTmp->Right();
					mark = 1;
				}
			}

			NodeType* pNewNode = new NodeType(pElem);
			pNewNode->SetParent(pParent);

			assert(mark != 0);
			assert(pParent);
			if(mark == -1){
				pParent->SetLeft(pNewNode);
			}else{ // 1
				pParent->SetRight(pNewNode);
			}
			
			/**
			 * 初始化时自动设置nullptr与RED 
			 */ 
			// pNewNode->SetLeft(nullptr);
			// pNewNode->SetRight(nullptr);
			// pNewNode->RBColor.Color = RBAttribute::RED;
			//维护红黑树性质.
			assert(pNewNode);
			AddFixup(pNewNode);

		}else{
			root = new NodeType(pElem);
			root->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
		}
	}

private:
	NodeType* root;
private:
	void DelFixup(NodeType* pNode, const std::pair<NodeType*, char>& otherInfo){


	}

	//使pV的父节点指向pU,同时pU指向pV的父节点
    char TransPlant(NodeType* pV, NodeType* pU){
		char cTmp = 0;
        if(pV->Parent() == nullptr){
            root = pU;
        }else
        if(pV->Parent()->pLeft == pV){
            pV->Parent()->pLeft = pU;
			cTmp = -1;
        }else{
            pV->Parent()->pRight = pU;
			cTmp = 1;
        }

		assert(pU);
		pU->SetParent(pV->Parent());
		return cTmp;
    }

	void LeftRotate(NodeType* pNode){
		assert(pNode);
		NodeType* pTmp = pNode->Right();
		assert(pTmp);

		pNode->SetRight(pTmp->Left());
		if(pTmp->Left()){
			pTmp->Left()->SetParent(pNode);
		}

		pTmp->SetParent(pNode->Parent());

		if(pNode->Parent() == nullptr){
			//root节点
			root = pTmp;
		}else
		if(pNode->Parent()->Left() == pNode){
			pNode->Parent()->SetLeft(pTmp);
		}else
		if(pNode->Parent()->Right() == pNode){
			pNode->Parent()->SetRight(pTmp);
		}


		pTmp->SetLeft(pNode);
		pNode->SetParent(pTmp);
	}

	void RightRotate(NodeType* pNode){
		assert(pNode);
		NodeType* pTmp = pNode->Left();
		assert(pTmp);

		pNode->SetLeft(pTmp->Right());
		if(pTmp->Right()){
			pTmp->Right()->SetParent(pNode);
		}

		pTmp->SetParent(pNode->Parent());

		if(pNode->Parent() == nullptr){
			//root 节点
			root = pTmp;
		}else
		if(pNode->Parent()->Left() == pNode){
			pNode->Parent()->SetLeft(pTmp);
		}else
		if(pNode->Parent()->Right() == pNode){
			pNode->Parent()->SetRight(pTmp);
		}

		pTmp->SetRight(pNode);
		pNode->SetParent(pTmp);
	}

	void AddFixup(NodeType* pNode){
		//执行到while循环内不需要担心祖节点或父节点是否为nullptr的问题，
		//首先由外部插入一定存在一个root,其次由while条件保护，所以当执行到while语句内时，
		//一定存在三个节点，root、父节点、祖节点.
		//父结点若为红则表明需要修复，因为破坏了性质4,红色的节点必须有两个黑色的子节点.
		while(pNode && pNode->Parent() && pNode->Parent()->RBColor.IsRed()){
			//父节点是祖节点的左子树还是右子树.
			//关系到叔节点性质的维护.
			if(pNode->Parent() == pNode->Parent()->Parent()->Left()){
				NodeType* pUncleNode = pNode->Parent()->Parent()->Right();
				//若叔节点为红色，则需要维护性质，此时祖父一定为黑色(根据性质4未被破坏时判断来说).
				if(pUncleNode && pUncleNode->RBColor.IsRed()){
					//情况1
					pUncleNode->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::RED;
					//此时修复的范围就是在祖节点以下，祖节点之上的冲突并未修复(之上的节点未知是否会违反性质4).
					pNode = pNode->Parent()->Parent();
				}else{
					if(pNode->Parent()->Right() == pNode){
						//情况2
						//可能由情况1转为情况2，
						//也可能直接进入情况2
						pNode = pNode->Parent();
						LeftRotate(pNode);
					}

					//情况3
					//可能由情况2转为情况3
					//也可能直接进入情况3
					pNode->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::RED;
					RightRotate(pNode->Parent()->Parent());
				}
			}else{ //右
				NodeType* pUncleNode = pNode->Parent()->Parent()->Left();
				//若叔节点为红色，则需要维护性质，此时祖父一定为黑色(根据性质4未被破坏时判断来说).
				if(pUncleNode && pUncleNode->RBColor.IsRed()){
					//情况1
					pUncleNode->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::RED;
					//此时修复的范围就是在祖节点以下，祖节点之上的冲突并未修复(之上的节点未知是否会违反性质4).
					pNode = pNode->Parent()->Parent();
				}else{
					if(pNode->Parent()->Left() == pNode){
						//情况2
						//可能由情况1转为情况2，
						//也可能直接进入情况2
						pNode = pNode->Parent();
						RightRotate(pNode);
					}

					//情况3
					//可能由情况2转为情况3
					//也可能直接进入情况3
					pNode->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
					pNode->Parent()->Parent()->RBColor.Color = RBAttribute::COLOR_DEF::RED;
					LeftRotate(pNode->Parent()->Parent());
				}
			}

			root->RBColor.Color = RBAttribute::COLOR_DEF::BLOCK;
		}
	}

	
};

#endif /* !RBTREE_H_ */
